package com.fanshuai.algorithms.dynamic;

import java.util.Arrays;

public class Sequence {
    /**
     * 最长递增子序列: 给定一个无需的整数数组，求最长增长的子序列长度。
     * 动态规划解法：
     * dp table: dp[n]表示以a[n]为结尾的最长增长的子序列长度。
     * 状态转移方程：
     * dp[n] = if (a[i] < a[n]) max(dp[i] + 1, dp[n]), 对任意0<=i<n。
     * bad case：dp[0]=1
     * @param a
     * @return
     */
    public static void LIS(int[] a) {
        int[] dp = new int[a.length];
        // dp 数组全都初始化为 1
        Arrays.fill(dp, 1);
        for (int i = 1; i < a.length; i++) {
            for (int j = 0; j < i; j++) {
                if (a[j] < a[i]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
        }

        int len = 0;
        int index = -1;
        for (int i = 0; i < dp.length; i++) {
            if (dp[i] > len) {
                len = dp[i];
                index = i;
            }
        }

        int[] sub = new int[len];
        int pos = sub.length - 1;
        sub[pos--] = a[index];
        for (int i = index - 1; i >= 0; i--) {
            if (dp[index] == dp[i] + 1) {
                sub[pos--] = a[i];
                index = i;
            }
        }

        for (int i = 0; i < sub.length; i++) {
            System.out.println(sub[i]);
        }
    }

    /**
     * 最长公共子序列（Longest Common Subsequence，简称 LCS）是一道非常经典的题目
     * 输入: str1 = "abcde", str2 = "ace"
        输出: 3
        解释: 最长公共子序列是 "ace"，它的长度是 3

     动态规划解法：
     dp table: dp[i][j]表示子串s1[1..i]和s2[1..j]的最长公共子序列长度。字符串索引从1开始
     状态转移方程：
     dp[i][j] = if (s1[i-1] == s2[j-1]) {
        dp[i-1][j-1] + 1
     } else {
        max(dp[i-1][j], dp[i][j-1])
     }
     bad case: dp[0][j]=dp[i][0]=0
     * @return
     */
    public static String LCS(String s1, String s2) {
        if (null == s1 || null == s2) {
            return "";
        }

        int len1 = s1.length();
        int len2 = s2.length();
        int[][] dp = new int[len1 + 1][len2 + 1];

        /**
         * 根据bad case，确定dp table边界
         * 根据状态转移方程，确定迭代顺序，迭代求取dp table
         */
        for (int i = 0; i <= len1; i++) {
            dp[i][0] = 0;
        }
        for (int j = 0; j <= len2; j++) {
            dp[0][j] = 0;
        }
        for (int i = 1; i <= len1; i++) {
            for (int j = 1; j <= len2; j++) {
                char c1 = s1.charAt(i - 1);
                char c2 = s2.charAt(j - 1);
                if (c1 == c2) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }

        /**
         * dp table只表示某种最优值，求解具体的公共子序列时，需要从dp[m][n]回溯，知道dp[0][0]
         * 回溯过程中，遵循状态转移方程的最优选择，回退指针
         */
        char[] commonS = new char[dp[len1][len2]];
        int k = commonS.length - 1;

        int m = len1, n = len2;
        while (m > 0 || n > 0) {
            char c1 = s1.charAt(m - 1);
            char c2 = s2.charAt(n - 1);
            if (c1 == c2) {
                commonS[k--] = c1;
                m--;
                n--;
            } else {
                if (dp[m - 1][n] > dp[m][n - 1]) {
                    m--;
                } else {
                    n--;
                }
            }
        }

        return new String(commonS);
    }

    public static void main(String[] args) {
        int a[] = {10, 9, 2, 5, 3, 7, 101, 18, 2, 3, 120};
        //LIS(a);

        String str1 = "abcde", str2 = "ace";
        System.out.println(LCS(str1, str2));
    }
}
